Static checking for program correctness, while currently an area of great promise and ongoing investigation, is fundamentally unable to detect large classes of program defects that are nevertheless very important. Software testing addresses these shortcomings but is expensive and limited by the scenarios used, and the amount of testers and time allotted. Consequently, software continues to ship with latent bugs, which can compromise system security in addition to affecting reliability. Furthermore, even “correct” software can violate a higher-level security policy. Given this, a pragmatic approach is to self-monitor application execution and report encountered defects.
One method for finding latent software defects is runtime monitoring. Runtime monitoring of an executing program can identify many program defects that static checking may miss, such as memory leaks, data races, and invariance. Runtime monitoring can be implemented by instrumenting code. Instrumentation refers to the process of adding code to software that monitors and collects data regarding memory management and other details of the software at runtime. However, currently, the overhead added to the executing program can exceed 30%, a slowdown that users are likely to notice and software developers are unlikely to accept. One solution is burst sampling.
The sequence of all events occurring during execution of a program is generally referred to as the “trace.” A “burst” on the other hand is a subsequence of the trace. Arnold and Ryder present a framework that samples bursts. (See, M. Arnold and B. Ryder, “A Framework For Reducing The Cost Of Instrumented Code,” Programming Languages Design And Implementation (PLDI) (2001).) In their framework, the code of each procedure is duplicated. (Id., at FIG. 2.) Both versions of the code contain the original instructions, but only one version is instrumented to also collect profile information. The other version only contains checks at procedure entries and loop back-edges that decrement a counter “nCheck,” which is initialized to “nCheck0.” Most of the time, the (non-instrumented) checking code is executed. Only when the nCheck counter reaches zero, a single intraprocedural acyclic path of the instrumented code is executed and nCheck is reset to nCheck0.
A limitation of the Arnold-Ryder framework is that it stays in the instrumented code only for the time between two checks. Since it has checks at every procedure entry and loop back-edge, the framework captures a burst of only one acyclic intraprocedural path's worth of trace. In other words, only the burst between the procedure entry check and a next loop back-edge is captured. This limitation can fail to profile many longer “hot data stream” bursts, and thus fail to optimize such hot data streams. Consider for example the code fragment:
for (i=0; i<n; i+ +)if (...) f( );else g( );Because the Arnold-Ryder framework ends burst profiling at loop back-edges, the framework would be unable to distinguish the traces fgfgfgfg and ffffgggg. For optimizing single-entry multiple-exit regions of programs, this profiling limitation may make the difference between executing optimized code most of the time or not.
Another limitation of the Arnold-Ryder framework is that the overhead of the framework can still be too high for dynamic optimization of machine executable code binaries. The Arnold-Ryder framework was implemented for a Java virtual machine execution environment, where the program is a set of Java class files. These Java programs typically have a higher execution overhead, so that the overhead of the instrumentation checks is smaller compared to a relatively slow executing program. The overhead of the Arnold-Ryder framework's instrumentation checks may make dynamic optimization with the framework impractical in other settings for programs with lower execution overhead (such as statically compiled machine code programs).
A framework that supports bursty tracing for low-overhead temporal profiling is described in Chilimbi, T. and Hirzel, M., “Bursty Tracing: A Framework for Low-Overhead Temporal Profiling,” in Workshop on Feedback-Directed and Dynamic Optimizations (FDDO), 2001; and Chilimbi, T. and Hirzel, M., “Dynamic Hot Data Stream Prefetching For General-Purpose Programs,” in PLDI '02, Jun. 17-19, 2002. This bursty tracing framework adds a second counter (nInstr) that controls the length of execution in the instrumented version of the code. In this way, the bursty tracing framework can periodically capture complete program execution detail (i.e., a “trace sample”) for short timeframes. Further, bursty tracing permits additional control and flexibility by allowing the “trace sample” extent to be configured in addition to collection frequency, by use of the two user-specified counters (nCheck and nInstr).
A drawback of the bursty tracing is that its sampling methodology may miss infrequently executed code paths that are nevertheless important for identifying reliability and/or security problems.